using System;
using System.Collections.Generic;
using System.Text;

namespace Mono.Graph.PriorityQueue
{
    public class FibonacciHeap<T> : IRangeIndexedPriorityQueue<T>
        where T : IComparable<T>
    {
        T[] Val;
        bool[] mark;
        int[] up;
        int[] left;
        int[] right;
        int[] down;
        int[] deg;
        int[] A;        
        bool[] exist;// do something about it !!!
        int Min;
        int size;
        IComparer<T> Cmp;
        public FibonacciHeap() { }
        public FibonacciHeap(int SizeOfHeap)
        {
            ((IRangeIndexedPriorityQueue<int>)this).Create(SizeOfHeap);
        }
        protected void heapLink(int a,int b) {
            deg[a]++;
            up[b] = a;
            right[left[b]] = right[b];
            left[right[b]] = left[b];
            if (down[a] > -1)
            {
                left[b] = left[down[a]];
                right[left[down[a]]] = b;
                left[down[a]] = b;
                right[b] = down[a];
            }
            else {
                down[a] = b;
                left[b] = right[b] = b;
            }
            mark[b] = false;
        }
        protected void linkRoot(int b) {
//            Console.WriteLine("linkRoot" + b);
            up[b] = -1;
            if (Min > -1)
            {
                int tmp = left[Min];
                left[Min] = b;
                right[b] = Min;
                right[tmp] = b;
                left[b] = tmp;
            }
            else 
            {
                Min = b;
                left[Min] = right[Min] = Min; 
            }
        }
        protected void consolidate() 
        {
 //           Console.WriteLine("cona " + Min);
            for (int i = 0; i < A.Length; i++)
            {
                A[i] = -1;
            }
            int maxdeg=-1;
//            Console.WriteLine("conbbb " + left[Min]);
            int il = 0;
            for (int i = Min ; (il == 0) || (i != Min); i = left[i], il++) 
            {
//                il++; 
 //               Console.Write(" " + i); 
            }
            
            int next = left[Min];
 //           Console.WriteLine("conb " + il +":"+next);
            
            for (int i = Min, j = il; j > 0; j--,i=next)
            {
//                Console.WriteLine("next" + next);
                next = left[i];
                int x = i;
                int d = deg[x];
//                Console.WriteLine("for" + i);
                while (A[d] != -1) {
                    int y = A[d];
                    if (Val[x].CompareTo(Val[y]) > 0) {//swap so that Vx<=Vy
                        int tmp = x;
                        x = y;
                        y = tmp;
                    } 
//                    Console.WriteLine("while" + x +" "+y);
                    this.heapLink(x,y);
                    A[d] = -1;
                    d++;
                }
                maxdeg=Math.Max(d,maxdeg);
                A[d] = x;
            }
            Min = -1;
            for (int i = 0; i <= maxdeg; i++) {
                if (A[i] > -1)
                {
                    linkRoot(A[i]);
                    if (Val[Min].CompareTo(Val[A[i]]) > 0) Min = A[i];
                }
            }

        }
        int IRangeIndexedPriorityQueue<T>.Size
        {
            get { return size; }
        }
        void IRangeIndexedPriorityQueue<T>.Create(int SizeOfHeap,IComparer<T> cmp)
        {
            Cmp = cmp;
            Val = new T[SizeOfHeap];
            mark = new bool[SizeOfHeap];
            up = new int[SizeOfHeap];
            down = new int[SizeOfHeap];
            left = new int[SizeOfHeap];
            right = new int[SizeOfHeap];
            deg = new int[SizeOfHeap];
            A = new int[(int)Math.Log(SizeOfHeap, 2) + 100];
            size = 0;
            Min = -1;

            exist = new bool[SizeOfHeap];
        }
        void IRangeIndexedPriorityQueue<T>.Create(int SizeOfHeap)
        {
            ((IRangeIndexedPriorityQueue<T>)this).Create(SizeOfHeap, Comparer<T>.Default);
        }
        void IRangeIndexedPriorityQueue<T>.Insert(int Key, T Value)
        {
            if (Min > -1)
            {
                linkRoot( Key);
                if (Val[Min].CompareTo(Value) > 0) Min = Key;
            }
            else {
                Min = Key;
                left[Key] = right[Key] = Key;
            }
            Val[Key] = Value;
            deg[Key] = 0;
            up[Key] = -1;
            down[Key] = -1;
            mark[Key] = false;
            exist[Key] = true;
            size++;
//            this.Validate();
        }
        void IRangeIndexedPriorityQueue<T>.DecreaseKey(int Key, T NewValue)
        {
            if((exist[Key])&&(Val[Key].CompareTo(NewValue)>0))
            {
                Val[Key] = NewValue;
                
                if ((up[Key] > -1) && (NewValue.CompareTo(Val[up[Key]]) < 0)) {
                    int y = up[Key]; int z;
                    int x=Key;
                        while ( (y > -1) ) {
                            if (left[x] == x)
                            {
                                down[y] = -1;
                                
                            }
                            else {
                                down[y] = left[x];
                                right[left[x]] = right[x];
                                left[right[x]] = left[x];
                            }
                            deg[y]--;
                            linkRoot(x);
                            up[x] = -1;
                            mark[x] = true;

                            z = up[y];
                            if ((z < 0)) break;
                            if (mark[y] == false) {
                                mark[y] = true;
                                break;
                            }
                            x = y;
                            y = z;
                        }
                }
                if (Val[Key].CompareTo(Val[Min]) < 0) Min = Key;
            }
//            Console.Write((this).ToString(null, null));
//            this.Validate();
        }
        int IRangeIndexedPriorityQueue<T>.TopKey
        {
            get
            {
                return Min;
            }
        }
        T IRangeIndexedPriorityQueue<T>.TopVal
        {
            get
            {
                return Val[Min];
            }
        }
        void IRangeIndexedPriorityQueue<T>.Pop()
        {
  //          if(size==1)Console.Write((this).ToString(null,null));
            int z = Min;
            int tmp = down[Min];
            if (tmp > -1)
            {
                int next = right[tmp];
                for (int i = next; i != tmp; i = next)
                {
                    next = right[next];
                    linkRoot(i);
                }
                linkRoot(tmp);
            }
            right[left[Min]] = right[Min];
            left[right[Min]] = left[Min];
            deg[Min] = -1;
            exist[Min] = false;
            if (size == 1) Min = -1;
            else {
                Min = left[Min];
                this.consolidate();
            }
            size--;
//            this.Validate();

        }
        T IRangeIndexedPriorityQueue<T>.GetVal(int indx)
        {
                if (exist[indx]) return Val[indx];
                throw new IndexOutOfRangeException("there is no index :" + indx + " on heap");
        }

        void IRangeIndexedPriorityQueue<T>.SetVal(int indx, T value)
        {
                if (exist[indx]) ((IRangeIndexedPriorityQueue < T > )this).DecreaseKey(indx, value);
                else ((IRangeIndexedPriorityQueue<T>)this).Insert(indx, value);
        }
        #region Debug
        /*
        private void zonk(string message) {
            Console.WriteLine(message);
            Console.Write(this.ToString(null, null));
        }
        public void Validate() {
            if (size < 1) return;
            if (up[Min] != -1)  zonk ("min not root");
            for (int i = 0; i < inserted.Length; i++)
            {
                if (!inserted[i]) continue;
                if (right[left[i]] != i) zonk("bad connection" + i);
                if (left[right[i]] != i) zonk("bad connection" + i);

            }
        }

        public string ToString(string format, IFormatProvider formatProvider)
        {
            StringBuilder ret = new StringBuilder();
            ret.Append("fibheap min:" + Min + "\n");
            for (int i = 0; i < Val.Length; i++)
            {
                ret.Append("node: i=" + i + " r=" + right[i] + " l=" + left[i] + " u=" + up[i] + " d=" + down[i] + "  deg=" + deg[i] + "   val="+((IFormattable)Val[i]).ToString(null,null) +"\n");
            }
            return ret.ToString();
            //            throw new Exception("The method or operation is not implemented.");
        }*/ 
        #endregion

    }



}
